The concept of group signature has been introduced in the early 90s for secure electronic payment applications, and from then onwards it has been widely applied in many other areas where a combination was needed of security (e.g. in terms of avoiding fraudulent behaviors or collusions of group members) and privacy (e.g. in terms of preserving anonymity of the group members).
As is known, group signatures are a particular sort of digital signatures, according to which members which are registered to a group are allowed to sign on behalf of the group, while preserving their anonymity. A verifier must be able to ascertain that the signature has been made by a member of the group, but he must not be allowed to trace the identity of the member. However, under certain circumstances, e.g. under a legal dispute, any group signature must be “openable”, in order to identify, without ambiguity, the identity of the signer. Moreover, nobody must be accorded the possibility to forge a group signature.
Each group may be managed by a central authority, who is in charge of registering new members willing to join the group and of revoking membership to previous members of the group, and who is able to “open” signatures to prove the real identity of the signer. This central authority is generally called group manager (GM), or even group leader or group center, while the participants of the group are called members or players. A group is called “dynamic” if members can join the group or be revoked from the group, or also have some associated parameters modified, during the group life cycle.
The following is a list of algorithms and procedures that any group signature scheme should provide:                SETUP: a procedure for the initialization of the group, and in particular for the definition of group parameters, and of group manager public and private keys;        JOIN: an interactive procedure between the group manager and a user willing to participate in the group, according to which the user identity is registered and, depending on the implementation, a secret or aggregation key, a certificate, or a membership information is provided to the user;        SIGN: an algorithm for the computation of a group signature of a message by a group member, as a function of his/hers personal data;        VERIFY: an algorithm which can be executed by any user (acting as a verifier) to prove that a group signature originated from a registered group member;        OPEN: an algorithm for the identification of the signer identity by the group manager, given a signed message, a valid group signature and group public data (and secret data known, ideally, only to the group manager); and        REVOKE: a procedure for the group manager to remove a member from the group, revoking his/her possibility to sign on behalf of the group.        
Moreover, the following is a list of properties which a group signature scheme should meet:                CORRECTNESS: a signature correctly generated by a group member must be recognized as valid by the VERIFY algorithm;        UNFORGEABILITY: only the group members must be able to sign messages on behalf of the group;        ANONIMITY (or UNTRACEABILITY): it must be computationally unfeasible (to everybody except the group manager) to trace the real identity of a signer from a valid group signature;        UNLINKABILITY: determining whether two group signatures stem from a same group member must be computationally unfeasible;        EXCULPABILITY (or NO-FRAMING): neither a coalition of group members, nor the group manager must be allowed to sign on behalf of another group member;        TRACEABILITY: the group manager must always be able to open a valid group signature and to determine the real identity of the signer; and        COALITION-RESISTANCE: any given subset of group members, sharing their respective secrets, must not be allowed to compute a valid group signature which is not openable by the group manager.        
Many group signature schemes have been proposed in the past, but so far none has proved to be completely satisfactory in terms of implemented procedures and properties.
In particular, D. Chaum and E. Van Heyst were among the first to introduce the concept of group signature in 1991 in their paper Group Signatures, In D. W. Davies, editor, Eurocrypt '91, volume 547 of LNCS, pages 257-265, Springer-Verlag, 1992. In their paper, Chaum and Van Heyst introduced the notion of group signature allowing the members of a group to sign data on behalf of the group, in such a manner that: only group members can sign messages; anyone is able to verify the validity of a group signature, but he/she is not allowed to know the identity of the signer; in case of a dispute, it is possible to open the signature (with or without the cooperation of the group members) to reveal the identity of the person that signed on behalf of the group. In particular, four different group signature schemes are proposed, which are not all based on the same cryptographic assumptions: the first one provides unconditional anonymity, while, according to the others, anonymity is protected computationally; moreover, in some schemes a centralized entity is required during the setup only, while in other schemes every member may create autonomously his group.
J. Benaloh, M. de Mare, One-Way Accumulators: A Decentralized Alternative to Digital Signatures, In: Advances in Cryptography—Eurocrypt '93, LNCS 765, pages 274-285, Springer-Verlag, Berlin, 1994, discloses the use of a one-way accumulator in cryptographic protocols, e.g. for membership testing. In particular, a function h(x, y) that is a one-way accumulator produces, given a starting value x0εX and a set of values y1, y2, . . . ymεY, a resulting value z, computed by the application of h, which is independent from the order of the yi values:z=h(h(h( . . . h(h(h(x,y1),y2),y3), . . . ym−2),ym−1),ym)In addition, the fact that h is a one-way accumulator means that given xεX and yεY it is computationally unfeasible to find, for a given y′εY, an x′εX such that h(x, y)=h(x′; y′). If the values y1, y2, . . . ym are associated to the users of a cryptosystem, the accumulated value z of all the yi can be computed, and a user holding a particular yj can compute a partial accumulated zj of all yi with i≠j. The holder of yj can then demonstrate that yj was a part of the original accumulated value z, by presenting zj and yj and proving that z=h(zj; yj). A person who wishes to forge a particular y′ would be faced with the problem of constructing an x′ with the property that z=h(x′; y′), i.e. a computationally unfeasible computation. As function h, the authors suggest the use of a modular exponential function:h(x,y)=xy mod n where n is a large rigid integer (i.e. n=(2p′+1)(2q′+1), with 2p′+1 and 2q′+1 safe primes, p′ and q′ odd primes, and |2p′+1|=|2q′+1|).
J. Camenisch and A. Lysyanskaya, Dynamic accumulators and application to efficient revocation of anonymous credentials, In: Crypto 2002, LNCS 2442, pages 61-76, Springer-Verlag, 2002, discloses another scheme based on the use of accumulators. In particular, this scheme uses a dynamic accumulator, i.e. an accumulator that allows to dynamically add and delete inputs, such that the cost of an add or delete is independent of the number of accumulated values. The scheme allows a group member to produce a simplified and efficient authorization proof, that is, having the property that the complexity of the signature verification and group membership verification are independent from the number of currently revoked group members or total group members. According to an aspect of this scheme, in a setup procedure, the group manager chooses a number of precomputed values ei and accumulates them in order to compute a group public key u, as:u=fn(u,Πei)wherein fn is a dynamic accumulator function; in particular, the number of precomputed values ei is equal to a maximum number of users that can join the group. In a join procedure, the group manager assigns to the new member a respective one of the precomputed values ei (in particular, a value that was not yet associated to existing members), and computes a membership value ci for the new member, as:
      c    i    =      u          1              e        i            i.e. as a function of the group public key u, and the inverse 1/ei of the associated precomputed value. Accordingly, updates by the group manager and/or by the group members are required only in case of deletion of members, or in the event that the group manager runs out of precomputed values ei.